/**
 * FileName: L354
 * Author:   powersi
 * Date:     2021/3/4 10:29
 * Description:
 */
package com.zm.demo.core.leetcode;

/**
 * //TODO
 * Description:
 * Author:      powersi
 * Date:        2021/3/4 10:29
 */
public class L354 {

    public static void main(String[] args) {
        //envelopes = [[5,4],[6,4],[6,7],[2,3]]
        int[][] envelopes = new int[4][2];
        envelopes[0] = new int[]{5,4};
        envelopes[1] = new int[]{6,4};
        envelopes[2] = new int[]{6,7};
        envelopes[3] = new int[]{2,3};
        new L354().maxEnvelopes(envelopes);
    }

    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0){
            return 0;
        }
        int [][]dp = new int[envelopes.length][envelopes.length];
        int max = 0;
        for (int i = 0; i < envelopes.length ; i++) {
            max = Math.max(max,calc(envelopes[i], envelopes, i, dp));
        }
        return max;
    }

    //计算每一个的套娃数，并计算出最大的那个值。
    public int calc(int []source, int[][] envelopes, int row, int[][]dp){
        int max = 1;
        for (int j = 0; j < envelopes.length ; j++) {
            if (row == j){
                continue;
            }else if (dp[row][j] != 0){
                max = Math.max(max, dp[row][j]);
            }else{
                int []compare = envelopes[j];
                if (source[0] < compare[0] && source[1]<compare[1]){
                    dp[row][j] = calc(compare, envelopes, j, dp)+1;
                    max = Math.max(max, dp[row][j]);
                }else {
                    dp[row][j] = -1;
                }
            }
        }
        return max;
    }
}
